﻿#define TRACE_1
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Threading;

namespace ProjectEulerSolutions.Problems
{
    /*
     * A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k.

For example, R(10) = 1111111111 = 11×41×271×9091, and the sum of these prime factors is 9414.

Find the sum of the first forty prime factors of R(109).

     * */
    class Problem132 : IProblem
    {
        SieveOfAtkin sieve;
        long[] p;

        public string Calculate()
        {
            p = new long[100000];
            p[0] = 2;

            sieve = new SieveOfAtkin(1000000);
            for (int i = 1, j = 3; i < p.Length; i++)
            {
                while (!sieve.IsPrime(j))
                    j += 2;
                p[i] = j;
                j += 2;
            }

            long[] precalc = { };//{ 11, 17, 41, 73, 101, 137, 251, 257, 271, 353, 401, 449, 641, 751, 1201, 1409, 1601, 3541, 4001, 4801, 5051 };

            foreach (long i in precalc)
                if (!sieve.IsPrime(i))
                    Console.WriteLine("Greška!");

            long sum;
            int count;
            int limit = 40;
            long k = (long)Math.Pow(10, 9);

            sum = precalc.Sum();
            count = precalc.Length;

            for (int j = 3; j < p.Length; j++)
            {
                long n = 0;
                for (int i = 1; i <= k; i++)
                {
                    n = n * 10 + 1;
                    n %= p[j];

                    if (n == 0)
                    {
                        if (k % i == 0)
                        {
                            break;
                        }
                        else
                        {
                            n = 1; // da ga ne prizna
                            break;
                        }
                    }
                }

                if (n == 0)
                {
                    sum += p[j];
                    count++;
                    Console.WriteLine("{0}: {1}", count, p[j]);

                    if (count == limit)
                        return sum.ToString();
                }
            }

            return sum.ToString();
        }
    }
}
